package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         0.1,
		Discription: "给定一组楼高度，返回从每栋楼往左右看能看到的楼的数量（往右看时，如果h[i]>=h[i+1,i+1将不可见；往左边看同理）",
		Level:       2,
		Labels: map[string]int{
			"单调栈": 1,
		},
	})
}

//从i处能看到的楼的数量：
//i自己
//从右往左：h[i+1:]中以h[i+1]开始的单调递增序列的长度
//从左往右：h[:i]中以h[i-1]结尾的单调递减序列长度
func CanSeeNum(h []int) []int {
	n := len(h)
	s1 := make([]int, 0)
	res := make([]int, n)
	for i := 0; i < n; i++ {
		//当前s1的长度就是h[:i]中以h[i-1]结尾的从左往右单调递减序列的长度
		res[i] = len(s1) + 1
		for len(s1) > 0 && h[i] >= h[s1[len(s1)-1]] {
			s1 = s1[:len(s1)-1]
		}
		s1 = append(s1, i)
	}

	s2 := make([]int, 0)
	for i := n - 1; i >= 0; i-- {
		//当前s2的长度就是h[i+]中以h[i+1]为结尾的从右往左的单调递减序列的长度
		res[i] += len(s2)
		for len(s2) > 0 && h[i] >= h[s2[len(s2)-1]] {
			s2 = s2[:len(s2)-1]
		}
		s2 = append(s2, i)
	}

	return res
}
